package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-02-19 20:50
 **/
public class LeetCode969 {

    public List<Integer> pancakeSort(int[] arr) {
        int n = arr.length;
        //元素值 —》 索引
        int[] idxs = new int[n + 1];

        for (int i = 0; i < arr.length; i++) {
            idxs[arr[i]] = i;
        }

        List<Integer> ans = new ArrayList<>();

        for (int i = n; i >= 1; --i) {
            int idx = idxs[i];
            if (idx == i - 1) {
                continue;
            }

            if (idx != 0) {
                ans.add(idx + 1);
                reverse(arr, 0, idx, idxs);
            }

            ans.add(i);
            reverse(arr, 0, i - 1, idxs);
        }

        return ans;
    }

    void reverse(int[] arr, int l, int r, int[] idxs) {
        while (l < r) {
            idxs[arr[l]] = r;
            idxs[arr[r]] = l;
            int t2 = arr[l];
            arr[l] = arr[r];
            arr[r] = t2;
            ++l;
            --r;
        }
    }

}
